In data communications in a mobile radio communication network, since a bit error frequently occurs, an execution of an error correction processing is needed. In the error correction methods, there is a method in which a convolutional code generated from an input bit is decoded by Viterbi decoding on a receiver side. In the error correction processing, a digital signal processor (hereinafter referred to as “DSP”) is used.
The Viterbi decoding repeats the simple processing such as addition, comparison, and selection and performs a trace-back operation for finally data, thereby realizing a maximum likelihood decoding of the convolutional code.
The following will briefly explain the Viterbi decoding processing. The convolutional code is generated by mode 2 addition of input bits and a fixed number of bits precedent thereto. Then, a plurality of coding data is generated to correspond to one bit of the input bits. A number of input information bits having influence upon the coding data is called constraint length (K). The number of input information bits is equal to a number of stages of shift registers used in mode 2 addition.
The coding data is determined by the input bits and a state of the preceding (K−1) input bits. When a new information bit is input, the state of the input bits transits to a new state. The state in which coding data transits is determined by whether the new input bit is “0” or “1”. Since the respective (K−1) bits are “1” or “0”, a number of states in which coding data transits becomes 2(K-1).
In the Viterbi decoding, received coding data sequence is observed, and the most-likely state is estimated from all obtainable state transitions. For this reason, every time when coding data (received data sequence) corresponding to one bit of information bits, an inter-signal distance (metric) of the respective paths to each state at that point is computed. Then, operations for leaving a path having a smaller metric among the paths reaching the same state as a survivor are sequentially repeated.
As shown in a state transition diagram of FIG. 1, in a convolutional encoder having a constraint length K, two paths each showing a state transition from each of state S[n] and S[n] and S[n+2(K-2)] at one previous point extend to a state S[2](n=positive integer) at a certain point. For example, in a case of K=3, a transition from each of S[1] (state S01) and S[3] (state S11) to S[2] (state S10) (state in which preceding two bits are input in order of “1” and “0”) at the time of n=1 is possible. Also, at the time of n=2, a transition from each of S[2] (state S10) and S[4] (state S00) to S[4] (state S00) (state shown by low-order two bits) is possible.
A path metric ‘a’ is a sum of an inter-signal distance (branch metric) “x” between an output symbol of the path inputting to the state S[2n] and the received data sequence and a path metric “A.” The path metric “A” is the total sum of branch metrics of the survivor paths up to the state S[n] at one previous state. Similarly, a path metric “b” is a sum of an inter-signal distance (branch metric) “y” between an output symbol of the path inputting to the state S[2n] and the received data sequence and a path metric “B.” The path metric “B” is the total sum of branch metrics of the survivor paths up to the state S[n+2(K-2)] at one previous point in the Viterbi decoding, the path metrics “a” and “b” inputting to the state S[2n] are compared with each other, and the smaller path is selected as a survivor path.
In the Viterbi decoding, each processing of addition for obtaining the path metric, comparison between the path metrics and the selection of path is executed with respect to 2(K-2) states at each point Moreover, in the selection of path, a history showing which path has been selected is left as a path select signal PS[i], [I=0 to 2(K-2)−1].
At this time, if a subscript (e.g., n) of one previous state of the selected path is smaller than a subscript (n+2K−2)) of one previous state of the non-selected other path, PS[i]=0 is established. If the subscript (n) it is larger than the subscript (n+2(K-2)), PS[i]=1 is established.
In the case of FIG. 1, since n<(n+2(K-2)) is established, the state S[n+2(K-2)] is selected at the time of a>b and PS[S2n]=1 is established, and the state S[n] is selected at the time of a≦b and PS[S2n]=0 is established.
Then, in the Viterbi decoding, data is decoded while being traced back to the path finally survived based on the path select signal.
The following will explain the conventional processing unit for Viterbi decoding, TMS320C54x, which is a general processing unit, (manufactured by TEXAS INSTRUMENTS, hereinafter referred to as “C54x”) being given as one example. In a GSM cellular radio system, equation (1) set forth below is used as a convolutional code.G1 (D)=1+D3+D4G2(D)=1+D+D3+D4  (1)
The above convolutional code is expressed by a trellis diagram of a butterfly structure shown in FIG. 2. The trellis diagram shows a state in which the convolutional code transits from a certain state to another state. Let us assume that constraint length K is 5. States of 2(K-2)=16 or 8 butterfly structures are present for each symbol section. Then, two branches are input in each state, and a new path metric is determined by the ACS operations
The branch metric can be defined as the following equation (2).M=SD(2*i)*B(J,0)+SD(2*i+1)*B(j,1)  (2)where SD(2*i) denotes a first symbol of a symbol metric showing a soft decision input, and SD(2*i+1) denotes a second symbol of the symbol metric. B(J,0) and B(j,1) conform to codes generated by a convolutional encoder as shown in FIG. 3.
In C54x, an arithmetic logic section (hereinafter referred to as “ALU”) is set to a dual 16-bit mode, thereby processing the butterfly structure at high speed. The determination of a new path metric (j) can be obtained by calculating two path metrics (2*J and 2*J+1) and the branch metrics (M and −M) in parallel based on a DSADT instruction and executing a comparison based on a CMPS instruction. The determination of a new path metric (j+8) can be obtained by calculating two path metrics and the branch metrics (M and −M) in parallel based on the DSADT instruction. The calculation results are stored in high and low order bits of a double-precision accumulator, respectively.
The CMPS instruction compares the high and low order bits of the accumulator and stores a larger value in a memory. Also, every time when the comparison is executed, which value is selected is written in a 16-bit transition register (TRN). The content written to the TRN is stored in the memory every time when each symbol processing is ended. Information to be stored in the memory is used to search a suitable path in the trace-back processing. FIG. 4 shows a macro program for a butterfly operation of the Viterbi decoding.
The values of the branch metrics are stored in the T register before the macro is called. FIG. 5 shows an example of a memory mapping of the path metrics.
8 butterfly operations are executed in one symbol section and 16 new states are obtained. This series of processing is repeatedly computed over several sections. After the end of the processing, the trace-back is executed so as to search a suitable path from 16 paths. Thereby, a decoding bit sequence can be obtained.
The mechanism of the ACS operations of the C54x, which is the general DSP can be thus explained. Then, in C54x, and the updates of two path metrics are realized with 4 machine cycles from the example of the macro program of FIG. 4.
In the future, there is expected an increase in demand for non-voice communications requiring high quality transmission with a lower bit error rate than voice communications. As means for achieving the low bit error rate, there is means for increasing the constraint length K of the Viterbi decoding.
However, if the constraint length is increased by a value corresponding to one bit, a number of path metrics (number of states) doubles. For this reason, a number of operations in the Viterbi decoding using DSP double. Generally, an amount of information in non-voice communications is larger than the amount of information in voice communications. If the amount of information increases, the number of operations in the Viterbi decoding including the ACS operation also increases. An increase in number of operations using DSP makes it difficult to maintain a battery for a portable terminal for a long period of time.
For the purpose of downsizing the portable terminal, reducing the weight, and lowering the cost, an area processed by a special LSI has been also designed to be implemented in one chip form using a DSP processing in recent years.
However, an increase in the number of operations using DSP exceeds the processing capability of the existing DSP, thereby making it impossible to be implemented in one chip form using DSP.
Moreover, if the function of DSP is highly enhanced to increase the number of operations, an increase in the cost of DSP itself is brought about. As a result, the reduction in the cost of the portable terminal cannot be realized.